[清华集训2017]-无限之环

网络流

好神奇的题！

与联通性相关的最优性问题，先考虑插头dp，但是数据范围过大，gg。

观察图形发现是有限种上下左右的接口（注意直管不能翻转），而且是网格图，于是考虑费用流。（根本想不到且就算知道了也依旧不会做啊啊啊）

  • 怎么判断图是否漏水？

发现水在相邻的格子间流动，不漏等价于相邻格子间接口能对上，那么把接口抽象成管道就是 容量为 1 且必须满流。那么黑白染色，白点连 S，黑点连 T，每个格子分成上下左右中五个点，对于白点，中间指向周围；对于黑点，周围指向中间。这样满流，即流量等于接口数，就是不漏。（同时也有了让水流动的动力！）

考虑旋转怎么处理：改变的接口对应连边，注意容量都是 1，这样跑费用流的时候一个格子只能选一种状态。

代码在 uoj 上并没有 AC，T 了很多发，大概是建边不够优秀，然而不想改了。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
#include <bits/stdc++.h>
#define rep(i, x, y) for (int i = x; i <= y; i++)
using namespace std;

const int N = 2e3 + 10, inf = 0x3f3f3f3f;
int n, m, st, ed, idx, t1, t2, num;
int id[N][N][5];
const int dx[4] = {-1, 0, 1, 0}, dy[4] = {0, 1, 0, -1};

namespace MCMF {
    const int M = N * 5, MM = N * 100;  // 开足了！！！
    int lnk[M], fr[MM], to[MM], nxt[MM], cnt = 1, cap[MM], val[MM];
    int level[M], dis[M], pre[M], inq[M];
    queue<int> q;

    inline void add(int x, int y, int c, int v) {
        ++num;
        to[++cnt] = y, fr[cnt] = x, nxt[cnt] = lnk[x], lnk[x] = cnt, cap[cnt] = c, val[cnt] = v;
        to[++cnt] = x, fr[cnt] = y, nxt[cnt] = lnk[y], lnk[y] = cnt, cap[cnt] = 0, val[cnt] = -v;
    }

    inline void add2(int x, int y, int c, int v) {
        add(x, y, c, v), add(y, x, c, v);
    }

    inline bool spfa(int S, int T) {
        rep(i, 1, T) dis[i] = inf, pre[i] = inq[i] = 0;
        inq[S] = 1;
        q.push(S);
        while (q.size()) {
            int x = q.front(); q.pop(); inq[x] = 0;
            for (int i = lnk[x]; i; i = nxt[i]) {
                int y = to[i];
                if (cap[i] && dis[y] > dis[x] + val[i]) {
                    dis[y] = dis[x] + val[i];
                    pre[y] = i;
                    if (!inq[y]) q.push(y), inq[y] = 1;
                }
            }
        }
        return dis[T] != inf;
        return 1;
    }

    inline int McMf(int S, int T) {
        int cost = 0;
        while (spfa(S, T)) {
            --t1;
            cost += dis[T];
            for (int x = T; x != S; x = fr[pre[x]]) {
                cap[pre[x]]--, cap[pre[x] ^ 1]++;
            }
        }
        return t1 ? -1 : cost;
    }
}

int main() {
    using namespace MCMF;
    cin >> n >> m;
    rep(i, 1, n) rep(j, 1, m) rep(k, 0, 4) id[i][j][k] = ++idx;
    st = 0, ed = ++idx;
    rep(i, 1, n) rep(j, 1, m) {
        int x, cnt = 0; scanf("%d", &x);
        if ((i + j) & 1) {
            rep(k, 0, 3) if ((x >> k) & 1) add(id[i][j][4], id[i][j][k], 1, 0), ++cnt;
            rep(k, 0, 3) {
                int tx = i + dx[k], ty = j + dy[k];
                if (tx && ty && tx <= n && ty <= m) add(id[i][j][k], id[tx][ty][(k + 2) & 3], 1, 0);
            }
            add(st, id[i][j][4], cnt, 0);
            t1 += cnt;
        } else {
            rep(k, 0, 3) if ((x >> k) & 1) add(id[i][j][k], id[i][j][4], 1, 0), ++cnt;
            add(id[i][j][4], ed, cnt, 0);
            t2 += cnt;
        }

        if (x % 5 == 0) continue;

        if (cnt == 1) {
            rep(k, 0, 3) if ((x >> k) & 1) {
                add2(id[i][j][(k + 1) & 3], id[i][j][k], 1, 1);
                add2(id[i][j][(k + 3) & 3], id[i][j][k], 1, 1);
                add2(id[i][j][(k + 2) & 3], id[i][j][k], 1, 2);
            }
        } else if (cnt == 3) {
            rep(k, 0, 3) if (!((x >> k) & 1)) {
                add2(id[i][j][k], id[i][j][(k + 1) & 3], 1, 1);
                add2(id[i][j][k], id[i][j][(k + 3) & 3], 1, 1);
                add2(id[i][j][k], id[i][j][(k + 2) & 3], 1, 2);
            }
        } else if (cnt == 2) {
            rep(k, 0, 3) if ((x >> k) & 1) add2(id[i][j][k], id[i][j][(k + 2) & 3], 1, 1);
        }
    }
    // printf("%d\n", cnt);
    if (t1 != t2) return puts("-1"), 0;
    printf("%d\n", McMf(st, ed));
    return 0;
}